Most computers use a mass storage device, such as a fixed (or "hard") disk, to retain large quantities of information, such as application programs and data. Typically, the mass storage devices use a magnetic recording media to store the information, although newer devices use laser technology which reads information from a disk encoded with pits representing binary values. For personal computing, a mass storage device holding 20 to 40 megabytes is usually sufficient; however, computers used in business often use well in access of 40 megabytes. For computers used as servers on a network, 300 megabytes is generally required.
While state of the art fixed disks systems have access times of 16-18 milliseconds and data transfer rates of 600-1000 kilobytes/sec, the speed with which data may be retrieved from a fixed disk is significantly slower than the speed with which data may be retrieved from a semiconductor memory, such as a DRAM, and is much slower than the operating speed of the microprocessor. Hence, the microprocessor will remain idle for significant periods of time while it is waiting for data from the fixed disk. Consequently, caching systems, which store portions of the fixed disk's information within a semiconductor memory, have been developed to increase the effective speed of data transfers from the disk to the host computer.
A cache memory is typically situated between the host computer and the hard disk or other mass storage medium. The cache memory stores information from the hard disk which is expected to be the most frequently accessed. When the host computer requests a block of data from the hard disk, the contents of the cache memory are examined to determine whether the requested data is currently stored in the cache. If the data is in the cache memory (a "hit"), then the data is taken directly from the cache memory, thereby circumventing a disk access. If the data is not in the cache memory (a "miss"), then the requested information is read from the disk into the cache memory, and from the cache memory to the host computer.
The effectiveness of a cache memory depends upon a number of factors. Of primary importance are the method by which data is removed from the cache memory to provide space for new data and the method by which the contents of the cache memory may be read. The first concern, the method by which information is removed from the cache memory, is important because some types of information will be accessed more frequently than others. If frequently requested information is removed from the cache memory to provide room for new data from the disk, then the hit ratio will be significantly reduced. The second concern, the speed at which the contents of the cache may be read, is important because a determination of whether the requested information is stored in the cache memory must be made on every disk access request.
Prior art cache memory systems, while significantly improving the effective data transfer rate between the host computer and the mass storage medium, have not sufficiently addressed these problems. Therefore, a need has arisen in the industry for a mass storage controller having an efficient cache memory.